Atrist

# 题目: 301. 删除无效的括号

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

# 示例1:

输入：s = "()())()"
输出：["(())()","()()()"]

# 示例2:

输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

# 前提知识

  • 有效括号： 题目输入的字符串由一系列「左括号」和「右括号」组成，但是有一些额外的括号，使得括号不能正确配对。
  • 可以一次遍历计算出多余的「左括号」和「右括号」：如果当前遍历到的「左括号」的数目严格小于「右括号」的数目则表达式无效。
    • 当遍历到「左括号」的时候,left+1
    • 当遍历到「左括号」的时候
      • left !==0, --left
      • left==0, right++
    • 当遍历完，left和right就是各自最少应该删除的数量。

# 题解1： 回溯 和 剪枝

题中要求我们删除最少的括号数，并且要求得到所有的结果。

我们可以使用回溯法，尝试遍历所有可能的去掉非法括号的方案。

# 参考资料

← 326. 3的幂 →